ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpb/acm/CppApplication_1/main.cpp

   1 #include<iostream>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <vector>
   5 #include <algorithm>
   6 #include <list>
   7
   8 using namespace std;
   9 #define foreachin(it,s) for (typeof(s.begin()) it = (s).begin(); it != (s).end(); it++)
  10 #define forn(i,n) for(unsigned short i = 0; i < (n); i++)
  11
  12
  13 class uf_node{
  14 public:
  15 unsigned short name;
  16 unsigned short rank;
  17 uf_node *parent;
  18 };
  19
  20
  21 class union_find{
  22     public :
  23     uf_node* S;
  24     inline union_find(unsigned short n){
  25         S =new uf_node[n];
  26         for(unsigned short i=0;i<n;i++){
  27             S[i].rank=0;
  28             S[i].name=i;
  29             S[i].parent=&S[i];
  30         }
  31     }
  32     ~union_find(){delete[] S;}
  33
  34     inline void Union(unsigned short a, unsigned short b){ //use Union because union is a keyword :P
  35         unsigned short ranka,rankb;
  36         ranka=S[a].parent->rank;
  37         rankb=S[b].parent->rank;
  38         if(ranka>rankb){
  39             (S[b].parent)->parent=S[a].parent;
  40             S[a].rank=ranka+rankb;
  41         }
  42         else{
  43             (S[a].parent)->parent=S[b].parent;
  44             S[b].rank=ranka+rankb;
  45         }
  46     }
  47
  48     inline void compress_path(uf_node* temp, uf_node* aux, uf_node* stop_point){
  49         temp=aux->parent;
  50         aux->parent=stop_point;
  51         aux=temp;
  52         while(aux!=stop_point){
  53             temp=aux->parent;
  54             aux->parent=stop_point;
  55             aux=temp;
  56         }
  57     }
  58
  59     inline unsigned short Find(unsigned short a){
  60         uf_node* temp;
  61         uf_node* aux;
  62         unsigned short result;
  63         aux=&S[a];
  64         temp=S[a].parent;
  65         while(aux!=temp){
  66             aux=temp;
  67             temp=(*aux).parent;
  68         }
  69         result=aux->name;
  70         uf_node* stop_point;
  71         stop_point=aux;
  72         aux=&S[a];
  73         compress_path(temp,aux,stop_point);
  74
  75         return result;
  76     }
  77 };
  78
  79 class edge{
  80 public :
  81     unsigned short start,end;
  82     unsigned short cost;
  83     inline edge(unsigned short start, unsigned short end, unsigned short cost){
  84         this->start=start;
  85         this->end=end;
  86         this->cost=cost;
  87     }
  88 };
  89
  90
  91 inline bool compare(const edge& a,const edge& b ){
  92     return a.cost < b.cost;
  93
  94 }
  95
  96 inline void bucket_sort(list<edge>& e,unsigned short max_cost){
  97     vector<list<edge> > v(max_cost+1);
  98     while(!e.empty()){
  99         const edge& ed = e.front();
 100         v[ed.cost].push_back(ed);
 101         e.pop_front();
 102     }
 103     forn(i, max_cost+1){
 104         while(!v[i].empty()){
 105             e.push_back(v[i].back());
 106             v[i].pop_back();
 107         }
 108     }
 109
 110 }
 111
 112 inline unsigned short kruskal(list<edge>& e,unsigned short n, vector<list<edge> >& adj,list<edge>& rejected, unsigned short max_cost, unsigned short m){
 113     union_find list(n);
 114     unsigned short res=0;
 115     if (m > max_cost)
 116         bucket_sort(e,max_cost);
 117     else
 118         e.sort(compare);
 119
 120     foreachin(it,e){
 121         unsigned short s,f;
 122         s=it->start;
 123         f=it->end;
 124
 125         if(list.Find(s)==list.Find(f)){
 126
 127             rejected.push_back(*it);
 128             continue;
 129         }
 130         else{
 131             list.Union(s,f);
 132             res += it->cost;
 133             adj[s].push_back(*it);
 134             adj[f].push_back(edge(it->end,it->start,it->cost));
 135         }
 136     }
 137
 138     return res;
 139
 140 }
 141
 142
 143 inline void dfs_fill_max(unsigned short u, unsigned short x,vector<list<edge> >& mst_adjacency, vector<vector<edge*> >& max){
 144     foreachin(v,(mst_adjacency[x])){
 145        if( max[u][v->end] == NULL && v->end != u){
 146            if(x==u || v->cost > max[u][x]->cost){
 147                max[u][v->end] = &(*v);
 148            }
 149            else{
 150                max[u][v->end] = max[u][x];
 151            }
 152            dfs_fill_max(u,v->end,mst_adjacency,max);
 153        }
 154
 155     }
 156 }
 157
 158 inline unsigned short second_mst(unsigned short n, vector<list<edge> >& mst_adjacency, list<edge>& rejected,unsigned short minimum_cost){
 159     vector<vector<edge*> > max(n,vector<edge*>(n,NULL));
 160     list<edge>::iterator it = rejected.begin();
 161     unsigned short start = it->start;
 162     unsigned short end = it->end;
 163     dfs_fill_max(start,start,mst_adjacency, max);
 164     unsigned short old_cost=max[start][end]->cost;
 165     unsigned short new_cost=it->cost;
 166     unsigned short minimum= new_cost - old_cost;
 167     it++;
 168     for(it;it != rejected.end();it++ ){
 169         start = it->start;
 170         end = it->end;
 171         if(max[start][end] == NULL)dfs_fill_max(start,start,mst_adjacency, max);
 172
 173         unsigned short aux=it->cost- max[start][end]->cost;
 174         if(aux < minimum){
 175             if(aux == 0)return minimum_cost;
 176             minimum= aux;
 177             new_cost =  it->cost;
 178             old_cost = max[start][end]->cost;
 179         }
 180
 181     }
 182     return minimum_cost - old_cost + new_cost;
 183 }
 184
 185
 186 int main(){
 187 int cases;
 188 cin>>cases;
 189 unsigned short n;
 190 unsigned short m;
 191 unsigned short from,to,cost;
 192
 193
 194 while(cases > 0){
 195     scanf("%hu %hu",&n,&m);
 196     vector<list<edge> > mst_adjacency(n);
 197     list<edge> rejected;
 198     list<edge> l;
 199     unsigned short cant_edges=0;
 200     unsigned short max_cost = 0;
 201     while(cant_edges < m){
 202         scanf("%hu %hu %hu",&from,&to,&cost);
 203         if(cost > max_cost)max_cost = cost;
 204         l.push_back(edge(from-1,to-1,cost));
 205         cant_edges++;
 206     }
 207     unsigned short k =kruskal(l,n,mst_adjacency,rejected,max_cost,m);
 208     //unsigned short k =kruskal(l,n,mst_adjacency,rejected);
 209     cout << k<<" ";
 210     cout << second_mst(n,mst_adjacency,rejected,k)<<endl;
 211     cases--;
 212 }
 213 return 0;
 214 }
 215
 216
 217
 218
 219
 220